package com.xj.algorithm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * N叉树的最大深度
 */
public class L559_N叉树的最大深度 {

    /**
     * 给定一个 N 叉树，找到其最大深度。
     * <p>
     * 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
     * <p>
     * 例如，给定一个 3叉树 :
     * <p>
     *  
     * <p>
     * <p>
     * <p>
     *  
     * <p>
     * 我们应返回其最大深度，3。
     * <p>
     * 说明:
     * <p>
     * 树的深度不会超过 1000。
     * 树的节点总不会超过 5000。
     */
    public static void main(String[] args) {
        Node root1 = new Node(1);
        Node root2 = new Node(2);
        Node root3 = new Node(3);
        Node root4 = new Node(4);
        Node root5 = new Node(5);
        Node root6 = new Node(6);

        root3.children = new ArrayList<>();
        root3.children.add(root5);
        root3.children.add(root6);

        root1.children = new ArrayList<>();
        root1.children.add(root3);
        root1.children.add(root2);
        root1.children.add(root4);

        System.out.println(maxDepth(root1));
    }

    //自己的解法：递归
    public static int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }

        int max = 0;
        List<Node> list = root.children;
        if (list != null) {
            for (int i = 0; i < list.size(); i++) {
                Node node = list.get(i);
                int depth = maxDepth(node);
                max = max < depth ? depth : max;
            }
        }
        return max + 1;
    }
}

class Node {
    public int val;
    public List<Node> children;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
